package com.gxc.binarySearch;

/**
 * 寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 *
 * 算法的时间复杂度应该为 O(log (m+n))
 */
public class FindMedianSortedArrays {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;

        if (totalLength%2 == 1) {
            return findKNumber(nums1, nums2, (totalLength)/2+1);
        } else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (findKNumber(nums1, nums2, midIndex1 + 1) + findKNumber(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }

    public double findKNumber(int[] nums1, int[] nums2, int k) {
        int i = 0, j = 0;
        int m = nums1.length, n = nums2.length;

        while (true) {
            if (i == m) {
                return nums2[j + k - 1];
            }
            if (j == n) {
                return nums1[i + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[i], nums2[j]);
            }
            int index = k/2;
            int newi = Math.min(m, i + index)-1;
            int newj = Math.min(n, j + index)-1;
            if (nums1[newi]<=nums2[newj]) {
                k = k - (newi - i + 1);
                i = newi+1;
            } else {
                k = k - (newj - j + 1);
                j = newj+1;
            }

        }
    }

}
